package com.littrabble.sort;

/* int data[1..n]; */
public class Heap {

	public static void sort(int[] data, int n) {

		// create max heap tree
		for (int i = n / 2; i >= 1; i--) {
			adjust(data, i, n);
		}

		int tmp = data[1];
		data[1] = data[n];
		data[n] = tmp;

		for (int i = n - 1; i >= 2; i--) {
			adjust(data, 1, i);

			tmp = data[1];
			data[1] = data[i];
			data[i] = tmp;
		}
	}

	public static void adjust(int[] data, int index, int n) {

		int tmp = data[index];
		int j = 2 * index;
		boolean finish = false;

		while (j <= n && !finish) {
			if (j < n) {
				if (data[j] < data[j + 1]) {
					j++;
				}
			}

			if (tmp < data[j]) {
				data[j / 2] = data[j];
				j *= 2;
			} else {
				finish = true;
			}
		}

		data[j / 2] = tmp;
	}
}
